/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/best-time-to-buy-and-sell-stock
   @Language: C++
   @Datetime: 16-02-09 05:43
   */

class Solution {
public:
	/**
	 * @param prices: Given an integer array
	 * @return: Maximum profit
	 */
	int maxProfit(vector<int> &prices) {
		// write your code here
		int mx=INT_MAX, profit=0;
		for(int i=0; i<prices.size(); ++i){
			mx=min(mx,prices[i]);
			profit=max(profit,prices[i]-mx);
		}
		return profit;
	}
};
